// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
public class PalindromeLinkedList {

    public static void main(String[] args) {
        ListNode l1 = new ListNode();
        l1.val = 1;
        ListNode l2 = new ListNode();
        l2.val = 2;
        ListNode l3 = new ListNode();
        l3.val = 2;
        ListNode l4 = new ListNode();
        l4.val = 1;
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;

        isPalindrome(l1);
    }
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {  //空结点或者只有一个结点返回true
            return true;
        }
        ListNode slow = head;  //慢指针
        ListNode fast = head;  //快指针

        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        } //循环结束slow指向链表中点
        fast = fast.next == null ? fast : fast.next;

        ListNode end = fast;
        //slow结点开始往后翻转
        ListNode pre = null , cur = slow;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        //从前往后和从后往前依次遍历
        slow = head;
        boolean ret = true;
        while (slow != null && fast != null) {
            if(slow.val != fast.val) {
                ret = false;
                break;
            }
            slow = slow.next;
            fast = fast.next;
        }
        //恢复原链表
        cur = end;
        ListNode next = null;
        while (cur != null) {
            pre = cur.next;
            cur.next = next;
            next = cur;
            cur = pre;
        }
        System.out.println("===");
        return ret;
    }
}
